As it is known in the art, integrated circuits may be designed manually or with the use of logic synthesis tools. Logic synthesis tools are rule based or algorithmic processes that are used to translate boolean logic equations into circuit schematics.
One benefit of using logic synthesis for integrated circuit design is that a synthesized design can be done more rapidly than a manual design. One drawback of using logic synthesis is that the quality of the synthesized design is often inferior to that of a manually generated design in terms of circuit delay and area. Thus logic synthesis tools are generally used for designs that do not have strict timing or area constraints.
One case where synthesized logic is inferior to manually designed logic is fanout networks. Fanout networks are used when one gate must drive many loads but does not have the current capacity to drive the loads within the required times. A fanout network problem generally includes the following elements: a driving gate, having a known drive capability and input signal arrival time, a number of loads to be driven by the driving gate, each load having known capacitive load values and required input signal arrival times, and an available library of buffers of varying sizes and timing characteristics which can be used to drive the loads. A solution to the fanout problem comprises one or more buffers inserted in a certain configuration between the driving gate and the loads to provide the current capacity necessary for driving the loads in the required times. The fanout network should be optimized to use a minimal area for the distribution of signals while respecting the timing constraints. If all timing constraints cannot be met, a network is provided that exceeds the delay constraints by the smallest amount.
Fanout networks also help to reduce the propagation delay through a gate by reducing the gate's capacitive load. For example, if the output of a gate is coupled to n loads, the delay through the gate is O(n). By building a simple buffer tree at the output of the gate, the delay is reduced to O(log n).
Certain signals in the design may have critical timing constraints which, if not met, will cause the circuit to malfunction. A net on which a critical signal propagates is herein defined as a critical net, and a load receiving its input on a critical net is herein defined as a critical load. However, not all nets are critical, and each load driven by a gate generally has a distinct timing constraint. Ideally, a fanout network should be designed to provide the signal to the loads exactly when required. Loads with less restrictive timing constraints would be driven by latter portions of the fanout network, and thus all loads would be equally critical.
Fundamental fanout optimization techniques include buffer resizing and critical net isolation. Buffer resizing is a technique where the sizes of the transistors of the driving buffers are modified in order to meet the delay constraints for given output loads at a minimum cost in area. For example, the transistor size of a buffer driving a critical net may be increased to provide a faster drive to satisfy the timing constraint of an attached load. Similarly, the transistor size of a buffer driving a less critical net may be reduced to a size which keeps the timing constraint satisfied while reducing the area used for the fanout network.
Critical net isolation is used in fanout networks to provide the smallest number of buffers between the source and the critical load. A fanout network designed using critical net isolation may comprise two levels of buffering, where the first level includes one buffer for driving both the critical net and the second level of the fanout network. Because the critical net is driven by an earlier buffer stage, the propagation delay to the critical load is minimized.
Most existing methods for synthesizing fanout networks use the capacitive load and timing constraint information of each load to build iteratively a variety of buffer networks. Each buffer network is analyzed for area consumption and propagation delay. The results are compared against the best solution obtained so far, and discarded if the new configuration is not an improvement. The process described above is computationally intensive. The search space is limited by the amount of time deemed reasonable to allocate to fanout optimization within the entire design process. Due to the many sizes of buffers available for a fanout network design, and the many different ways to interconnect the buffers to drive the loads, finding an optimal fanout network by exhaustive search is unpractical for all but the simplest fanout problems.
One fanout optimization technique that restricts a priori the search space is the LT-tree method, described in "Performance-Oriented Technology Mapping", by Herve Touati, PhD Thesis, U. C. Berkeley, 1990. The LT-tree method considers only a subset of the set of all possible fanout tree networks and computes the fastest circuit within that subset. This subset is small enough to be searched exhaustively and still large enough to allow the buffering of loads while performing critical net isolation. A type 1 LT-Tree includes a chain of fanout buffers, each of which drives no more than one fanout buffer. A type 2 LT-tree also includes a chain of fanout buffers, with the last buffer in the chain potentially driving more than one buffer, wherein the buffers which are driven by the last buffer in the chain do not drive any other buffer.
A drawback of the methods described above for providing optimized fanout networks is that the size of the fanout network which is generated tends to be unnecessarily large. This is because the primary purpose of the methods described above is to minimize delay. Area minimization is performed as a secondary task. Large fanout networks are undesirable because the area used for the fanout network could alternatively be used to increase the logical function of the integrated circuits.